package BinaryTree;
//给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
class UseInAndPostOrderCreateTree {
    //创建一个节点：采用孩子表示法
    static class TreeNode {
        public int val;
        public TreeNode left;//储存左孩子的引用
        public TreeNode right;//储存右孩子的引用
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder, int inBegin, int inEnd) {
        //条件成立，证明已经二叉树已经递归到没有节点了
        if(inBegin > inEnd) {
            return null;
        }
        //创建一个二叉树的节点：
        TreeNode root = new TreeNode(postorder[postIndex]);
        //在中序遍历中找到根节点（前序遍历可知道根节点是哪一个）
        int rootIndex = findVal(inorder, inBegin, inEnd, postorder[postIndex]);
        postIndex--;
        //在中序遍历中 根据根节点 分为 左子树和右子树
        root.right = buildTreeChild(inorder, postorder, rootIndex + 1, inEnd);
        root.left = buildTreeChild(inorder, postorder, inBegin, rootIndex - 1);

        return root;
    }

    //在中序遍历中找到根节点（前序遍历可知道根节点是哪一个）
    public int findVal(int[] inorder, int inBegin, int inEnd, int val) {
        for(int i = inBegin; i <= inEnd; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}